import java.util.Arrays;

public class paixu {
    //  交换排序2种
                       //1.冒泡排序
    public static void maopao(String[] args) {
        int[] array =new int[]{1,3,4,2,7};
        for (int i = 0; i < array.length-1; i++) {
            int flag = 0;
            for (int j=0;j<array.length-i-1;j++){ //-i-1
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    flag=1;
                }
            }
            if(flag==0){
                break;
            }
        }
        System.out.println(Arrays.toString(array));
    }
                   //2.快速排序也是不管最后一个所以length-1  这是挖坑法
    public static void qsort(int[]arr,int low,int high) { //左边找小于基准的，右边找比基准大的交换
        if(low>=high){
            return;
        }
        int left =low;
        int right=high;
        int temp=arr[left];
        while (left<right){
            while (left<right&&arr[right]>=temp){
                right--;
            }
            arr[left]=arr[right];
            while (left<right&&arr[left]<=temp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=temp;
       qsort(arr,low,left-1);
       qsort(arr,left+1,high);
    }


   //两种插入排序
                  //1.插入排序优化
    public static void charu(int[] arr) {//稳定
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                } else {
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
                 //1.直接插入排序
    public static void cahru(int[] arr) {
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j>0;j--){
                if(arr[j-1]<=arr[j]){
                    break;
                }
               int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
    }

    //希尔排序
    public static void shell1(int[] arr,int gap) {
        for(int i=gap;i<arr.length;i++){
            int temp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                } else {
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }

    public static void shell(int[] arr) {
        int gap=arr.length;
        while (gap>1){
            shell1(arr,gap);
            gap/=2;
        }
        shell1(arr,1);
    }

    //两种选择排序
                // 1.简单选择排序 类似直接插入排序的优化，把第一个当成选择或插入的对象，选择是相互交换，插入是替换
    public static void select(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minindex=i;
            for (int j = i+1; j < arr.length; j++) {//不稳定
                if(arr[j]<arr[minindex]){
                    minindex=j;
                }
            }
            swap(arr,minindex,i);
        }
    }

    public static void swap(int[]arr,int i,int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }


     //堆排序
     public static void create(int[] arr) {
         for (int p=(arr.length-1-1)/2;p>=0;p--){
             shiftdown(arr,p,arr.length);
         }
     }

    public static void shiftdown(int[] arr,int inbegin,int len) { //从小到大排建立大堆，从大到小建立小堆，原因是插入数据时不会丢失数据
        int parent =inbegin;
        int child=2*parent+1;
        while (child<len){
            if(child+1<len&&arr[child]<arr[child]+1){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    public static void headsort(int[] arr) {
        create(arr);
        int end=arr.length-1;
        while (end>=0){
            swap(arr,0,end);
            shiftdown(arr,0,end);
            end--;
        }
    }
    /**
     * Hoare 法
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partitionHoare(int[] array,int low,int high) {
        int i = low;
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            //此时high就是你要找的数字
            while (low < high && array[low] <= tmp) {
                low++;
            }
            //此时low就是你要找的数字
            swap(array,low,high);
        }
        swap(array,low,i);
        return low;
    }

    /**
     * 挖坑法
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partitionHole(int[] array,int low,int high) {
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }


    /**
     * 双指针1
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition1(int[] array,int low,int high) {
        int prev = low ;
        int cur = low+1;
        while (cur <= high) {
            if(array[cur] < array[low] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,low);
        return prev;
    }

    /**
     * 双指针2
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int d = left + 1;
        int pivot = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                swap(array, i, d);
                d++;
            }
        }
        swap(array, d - 1, left);
        return d - 1;
    }

    public static void insertSortRange(int[] array,int low,int end) {
        for(int i = low+1;i <= end;i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= low ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 找到三个数中间大小的数字的下标
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int medianOfThreeIndex(int[] array,int left,int right) {
        int mid = left + (right-left)>>>1;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if( array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

    //[left,right]
    private static void quick(int[] array,int left,int right) {
        if(left >= right) return;

        //1、在某个区间的时候，使用直接插入排序【优化的区间内的比较】
        if(right-left+1 <= 70000) {
            //进行插入排序：
            insertSortRange(array, left, right);
            return;
        }

        //2、三数取中法【优化的是你本身的分割,减少递归的深度】
        int index = medianOfThreeIndex(array, left, right);
        swap(array,left,index);

        //TODO: 3、将基准相同的数字 靠到跟前 从而减少递归的区间

        int pivot = partitionHole(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    /**
     * 时间复杂度：
     *    好的情况下：O(n*logn)   最坏： 有序或者逆序：O(n^2)
     * 空间复杂度：
     *    好的情况下：logn      最坏：O(n)
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    /**
     * 非递归实现快速排序
     * @param array
     */
    public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partitionHole(array,left,right);
        //左边有2个数据及以上
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partitionHole(array,left,right);
            //左边有2个数据及以上
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    /**
     * 合并！
     * @param array
     * @param low
     * @param mid
     * @param high
     */
    private static void merge(int[] array,int low,int mid,int high) {

        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;

        int[] tmpArr = new int[high-low+1];
        int k = 0;//代表tmpArr的下标
        //证明两个段都有数据
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        //剩余元素，全部挪过来
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        //剩余元素，全部挪过来
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+low] = tmpArr[i];
        }
    }

    private static void mergeSortInternal(int[] array,int low,int high) {
        if(low >= high) return;
        int mid = low+((high-low)>>>1);

        mergeSortInternal(array,low,mid);

        mergeSortInternal(array,mid+1,high);
        merge(array,low,mid,high);
    }

    /**
     * 时间复杂度：N*logN【和数据是否有序没有关系】
     * 空间复杂度：O(n)
     * 稳定性：稳定的排序
     * 插入  冒泡   归并
     * @param array
     */
    public static void mergeSort(int[] array) {
        mergeSortInternal(array,0,array.length-1);
    }

    /**
     * 非递归的归并排序
     *
     * @param array
     */
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += 2*gap) {
                int left = i;
                int mid = left+gap-1;
                //修正mid
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;
                //修正right
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

    /**
     * 计数排序：
     * 时间复杂度：O(范围+N)
     * 空间复杂度：O(范围)
     * 计数排序和当前数据给定的范围是有关系的。
     *         int range = maxVal-minVal+1;
     *         集中的就好点；  0-100-》10
     * 稳定性：
     * @param array
     */
    public static void countSort(int[] array) {
        //1、获取最大值和最小值
        int maxVal = array[0];
        int minVal = array[0];
        //O(N)
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //2、开始计数
        int range = maxVal-minVal+1;
        int[] count = new int[range];
        //O(N)
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        //3、遍历这个计数数组，把数据放回array
        //O(范围 + n), 某一次 可能是n次
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                array[index++] = i+minVal;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {6,1,6,3,4,2,10,9,36,45,8,19};
        System.out.println("排序前："+ Arrays.toString(array));
        countSort(array);
        System.out.println("排序后："+ Arrays.toString(array));
    }
}
}
